/* -*- Mode: java; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
 *
 * ***** BEGIN LICENSE BLOCK *****
 * Version: MPL 1.1/GPL 2.0
 *
 * The contents of this file are subject to the Mozilla Public License Version
 * 1.1 (the "License"); you may not use this file except in compliance with
 * the License. You may obtain a copy of the License at
 * http://www.mozilla.org/MPL/
 *
 * Software distributed under the License is distributed on an "AS IS" basis,
 * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
 * for the specific language governing rights and limitations under the
 * License.
 *
 * The Original Code is Rhino code, released
 * May 6, 1999.
 *
 * The Initial Developer of the Original Code is
 * Netscape Communications Corporation.
 * Portions created by the Initial Developer are Copyright (C) 1997-2000
 * the Initial Developer. All Rights Reserved.
 *
 * Contributor(s):
 *   Igor Bukanov
 *
 * Alternatively, the contents of this file may be used under the terms of
 * the GNU General Public License Version 2 or later (the "GPL"), in which
 * case the provisions of the GPL are applicable instead of those above. If
 * you wish to allow use of your version of this file only under the terms of
 * the GPL and not to allow others to use your version of this file under the
 * MPL, indicate your decision by deleting the provisions above and replacing
 * them with the notice and other provisions required by the GPL. If you do
 * not delete the provisions above, a recipient may use your version of this
 * file under either the MPL or the GPL.
 *
 * ***** END LICENSE BLOCK ***** */

package org.mozilla.javascript;

import java.io.*;

/**
 * Map to associate non-negative integers to objects or integers. The map does
 * not synchronize any of its operation, so either use it from a single thread
 * or do own synchronization or perform all mutation operations on one thread
 * before passing the map to others.
 * 
 * @author Igor Bukanov
 * 
 */

public class UintMap implements Serializable {
  static final long serialVersionUID = 4242698212885848444L;

  // Map implementation via hashtable,
  // follows "The Art of Computer Programming" by Donald E. Knuth

  // A == golden_ratio * (1 << 32) = ((sqrt(5) - 1) / 2) * (1 << 32)
  // See Knuth etc.
  private static final int A = 0x9e3779b9;

  private static final int EMPTY = -1;

  private static final int DELETED = -2;

  private static int tableLookupStep(int fraction, int mask, int power) {
    int shift = 32 - 2 * power;
    if (shift >= 0)
      return fraction >>> shift & mask | 1;
    else
      return fraction & mask >>> -shift | 1;
  }

  private transient int[] keys;

  private transient Object[] values;

  private int power;

  private int keyCount;

  private transient int occupiedCount; // == keyCount + deleted_count

  // If ivaluesShift != 0, keys[ivaluesShift + index] contains integer
  // values associated with keys
  private transient int ivaluesShift;

  public UintMap() {
    this(4);
  }

  public UintMap(int initialCapacity) {
    if (initialCapacity < 0)
      Kit.codeBug();
    // Table grow when number of stored keys >= 3/4 of max capacity
    int minimalCapacity = initialCapacity * 4 / 3;
    int i;
    for (i = 2; 1 << i < minimalCapacity; ++i) {
    }
    power = i;
    if (true && power < 2)
      Kit.codeBug();
  }

  public void clear() {
    int N = 1 << power;
    if (keys != null) {
      for (int i = 0; i != N; ++i)
        keys[i] = EMPTY;
      if (values != null)
        for (int i = 0; i != N; ++i)
          values[i] = null;
    }
    ivaluesShift = 0;
    keyCount = 0;
    occupiedCount = 0;
  }

  // Ensure key index creating one if necessary
  private int ensureIndex(int key, boolean intType) {
    int index = -1;
    int firstDeleted = -1;
    int[] keys = this.keys;
    if (keys != null) {
      int fraction = key * A;
      index = fraction >>> 32 - power;
      int entry = keys[index];
      if (entry == key)
        return index;
      if (entry != EMPTY) {
        if (entry == DELETED)
          firstDeleted = index;
        // Search in table after first failed attempt
        int mask = (1 << power) - 1;
        int step = tableLookupStep(fraction, mask, power);
        int n = 0;
        do {
          if (true) {
            if (n >= occupiedCount)
              Kit.codeBug();
            ++n;
          }
          index = index + step & mask;
          entry = keys[index];
          if (entry == key)
            return index;
          if (entry == DELETED && firstDeleted < 0)
            firstDeleted = index;
        } while (entry != EMPTY);
      }
    }
    // Inserting of new key
    if (true && keys != null && keys[index] != EMPTY)
      Kit.codeBug();
    if (firstDeleted >= 0)
      index = firstDeleted;
    else {
      // Need to consume empty entry: check occupation level
      if (keys == null || occupiedCount * 4 >= (1 << power) * 3) {
        // Too litle unused entries: rehash
        rehashTable(intType);
        keys = this.keys;
        return insertNewKey(key);
      }
      ++occupiedCount;
    }
    keys[index] = key;
    ++keyCount;
    return index;
  }

  private int findIndex(int key) {
    int[] keys = this.keys;
    if (keys != null) {
      int fraction = key * A;
      int index = fraction >>> 32 - power;
      int entry = keys[index];
      if (entry == key)
        return index;
      if (entry != EMPTY) {
        // Search in table after first failed attempt
        int mask = (1 << power) - 1;
        int step = tableLookupStep(fraction, mask, power);
        int n = 0;
        do {
          if (true) {
            if (n >= occupiedCount)
              Kit.codeBug();
            ++n;
          }
          index = index + step & mask;
          entry = keys[index];
          if (entry == key)
            return index;
        } while (entry != EMPTY);
      }
    }
    return -1;
  }

  /**
   * Get integer value assigned with key.
   * 
   * @return key integer value or defaultValue if key does not exist or does not
   *         have int value
   * @throws RuntimeException
   *           if key does not exist
   */
  public int getExistingInt(int key) {
    if (key < 0)
      Kit.codeBug();
    int index = findIndex(key);
    if (0 <= index) {
      if (ivaluesShift != 0)
        return keys[ivaluesShift + index];
      return 0;
    }
    // Key must exist
    Kit.codeBug();
    return 0;
  }

  /**
   * Get integer value assigned with key.
   * 
   * @return key integer value or defaultValue if key is absent
   */
  public int getInt(int key, int defaultValue) {
    if (key < 0)
      Kit.codeBug();
    int index = findIndex(key);
    if (0 <= index) {
      if (ivaluesShift != 0)
        return keys[ivaluesShift + index];
      return 0;
    }
    return defaultValue;
  }

  /** Return array of present keys */
  public int[] getKeys() {
    int[] keys = this.keys;
    int n = keyCount;
    int[] result = new int[n];
    for (int i = 0; n != 0; ++i) {
      int entry = keys[i];
      if (entry != EMPTY && entry != DELETED)
        result[--n] = entry;
    }
    return result;
  }

  /**
   * Get object value assigned with key.
   * 
   * @return key object value or null if key is absent
   */
  public Object getObject(int key) {
    if (key < 0)
      Kit.codeBug();
    if (values != null) {
      int index = findIndex(key);
      if (0 <= index)
        return values[index];
    }
    return null;
  }

  public boolean has(int key) {
    if (key < 0)
      Kit.codeBug();
    return 0 <= findIndex(key);
  }

  // Insert key that is not present to table without deleted entries
  // and enough free space
  private int insertNewKey(int key) {
    if (true && occupiedCount != keyCount)
      Kit.codeBug();
    if (true && keyCount == 1 << power)
      Kit.codeBug();
    int[] keys = this.keys;
    int fraction = key * A;
    int index = fraction >>> 32 - power;
    if (keys[index] != EMPTY) {
      int mask = (1 << power) - 1;
      int step = tableLookupStep(fraction, mask, power);
      int firstIndex = index;
      do {
        if (true && keys[index] == DELETED)
          Kit.codeBug();
        index = index + step & mask;
        if (true && firstIndex == index)
          Kit.codeBug();
      } while (keys[index] != EMPTY);
    }
    keys[index] = key;
    ++occupiedCount;
    ++keyCount;
    return index;
  }
  public boolean isEmpty() {
    return keyCount == 0;
  }

  // Structure of kyes and values arrays (N == 1 << power):
  // keys[0 <= i < N]: key value or EMPTY or DELETED mark
  // values[0 <= i < N]: value of key at keys[i]
  // keys[N <= i < 2N]: int values of keys at keys[i - N]

  /**
   * Set int value of the key. If key does not exist, also set its object value
   * to null.
   */
  public void put(int key, int value) {
    if (key < 0)
      Kit.codeBug();
    int index = ensureIndex(key, true);
    if (ivaluesShift == 0) {
      int N = 1 << power;
      // keys.length can be N * 2 after clear which set ivaluesShift to 0
      if (keys.length != N * 2) {
        int[] tmp = new int[N * 2];
        System.arraycopy(keys, 0, tmp, 0, N);
        keys = tmp;
      }
      ivaluesShift = N;
    }
    keys[ivaluesShift + index] = value;
  }
  /**
   * Set object value of the key. If key does not exist, also set its int value
   * to 0.
   */
  public void put(int key, Object value) {
    if (key < 0)
      Kit.codeBug();
    int index = ensureIndex(key, false);
    if (values == null)
      values = new Object[1 << power];
    values[index] = value;
  }

  private void readObject(ObjectInputStream in) throws IOException,
      ClassNotFoundException {
    in.defaultReadObject();

    int writtenKeyCount = keyCount;
    if (writtenKeyCount != 0) {
      keyCount = 0;
      boolean hasIntValues = in.readBoolean();
      boolean hasObjectValues = in.readBoolean();

      int N = 1 << power;
      if (hasIntValues) {
        keys = new int[2 * N];
        ivaluesShift = N;
      } else
        keys = new int[N];
      for (int i = 0; i != N; ++i)
        keys[i] = EMPTY;
      if (hasObjectValues)
        values = new Object[N];
      for (int i = 0; i != writtenKeyCount; ++i) {
        int key = in.readInt();
        int index = insertNewKey(key);
        if (hasIntValues) {
          int ivalue = in.readInt();
          keys[ivaluesShift + index] = ivalue;
        }
        if (hasObjectValues)
          values[index] = in.readObject();
      }
    }
  }
  private void rehashTable(boolean ensureIntSpace) {
    if (keys != null)
      // Check if removing deleted entries would free enough space
      if (keyCount * 2 >= occupiedCount)
        // Need to grow: less then half of deleted entries
        ++power;
    int N = 1 << power;
    int[] old = keys;
    int oldShift = ivaluesShift;
    if (oldShift == 0 && !ensureIntSpace)
      keys = new int[N];
    else {
      ivaluesShift = N;
      keys = new int[N * 2];
    }
    for (int i = 0; i != N; ++i)
      keys[i] = EMPTY;

    Object[] oldValues = values;
    if (oldValues != null)
      values = new Object[N];

    int oldCount = keyCount;
    occupiedCount = 0;
    if (oldCount != 0) {
      keyCount = 0;
      for (int i = 0, remaining = oldCount; remaining != 0; ++i) {
        int key = old[i];
        if (key != EMPTY && key != DELETED) {
          int index = insertNewKey(key);
          if (oldValues != null)
            values[index] = oldValues[i];
          if (oldShift != 0)
            keys[ivaluesShift + index] = old[oldShift + i];
          --remaining;
        }
      }
    }
  }
  public void remove(int key) {
    if (key < 0)
      Kit.codeBug();
    int index = findIndex(key);
    if (0 <= index) {
      keys[index] = DELETED;
      --keyCount;
      // Allow to GC value and make sure that new key with the deleted
      // slot shall get proper default values
      if (values != null)
        values[index] = null;
      if (ivaluesShift != 0)
        keys[ivaluesShift + index] = 0;
    }
  }

  public int size() {
    return keyCount;
  }

  private void writeObject(ObjectOutputStream out) throws IOException {
    out.defaultWriteObject();

    int count = keyCount;
    if (count != 0) {
      boolean hasIntValues = ivaluesShift != 0;
      boolean hasObjectValues = values != null;
      out.writeBoolean(hasIntValues);
      out.writeBoolean(hasObjectValues);

      for (int i = 0; count != 0; ++i) {
        int key = keys[i];
        if (key != EMPTY && key != DELETED) {
          --count;
          out.writeInt(key);
          if (hasIntValues)
            out.writeInt(keys[ivaluesShift + i]);
          if (hasObjectValues)
            out.writeObject(values[i]);
        }
      }
    }
  }

  /*
   * TEST START
   * 
   * public static void main(String[] args) { if (!check) {
   * System.err.println("Set check to true and re-run"); throw new
   * RuntimeException("Set check to true and re-run"); }
   * 
   * UintMap map; map = new UintMap(); testHash(map, 2); map = new UintMap();
   * testHash(map, 10 * 1000); map = new UintMap(30 * 1000); testHash(map, 10 *
   * 100); map.clear(); testHash(map, 4); map = new UintMap(0); testHash(map, 10
   * * 100); }
   * 
   * private static void testHash(UintMap map, int N) { System.out.print(".");
   * System.out.flush(); for (int i = 0; i != N; ++i) { map.put(i, i); check(i
   * == map.getInt(i, -1)); }
   * 
   * System.out.print("."); System.out.flush(); for (int i = 0; i != N; ++i) {
   * map.put(i, i); check(i == map.getInt(i, -1)); }
   * 
   * System.out.print("."); System.out.flush(); for (int i = 0; i != N; ++i) {
   * map.put(i, new Integer(i)); check(-1 == map.getInt(i, -1)); Integer obj =
   * (Integer)map.getObject(i); check(obj != null && i == obj.intValue()); }
   * 
   * check(map.size() == N);
   * 
   * System.out.print("."); System.out.flush(); int[] keys = map.getKeys();
   * check(keys.length == N); for (int i = 0; i != N; ++i) { int key = keys[i];
   * check(map.has(key)); check(!map.isIntType(key));
   * check(map.isObjectType(key)); Integer obj = (Integer) map.getObject(key);
   * check(obj != null && key == obj.intValue()); }
   * 
   * 
   * System.out.print("."); System.out.flush(); for (int i = 0; i != N; ++i) {
   * check(-1 == map.getInt(i, -1)); }
   * 
   * System.out.print("."); System.out.flush(); for (int i = 0; i != N; ++i) {
   * map.put(i * i, i); check(i == map.getInt(i * i, -1)); }
   * 
   * System.out.print("."); System.out.flush(); for (int i = 0; i != N; ++i) {
   * check(i == map.getInt(i * i, -1)); }
   * 
   * System.out.print("."); System.out.flush(); for (int i = 0; i != N; ++i) {
   * map.put(i * i, new Integer(i)); check(-1 == map.getInt(i * i, -1));
   * map.remove(i * i); check(!map.has(i * i)); map.put(i * i, i);
   * check(map.isIntType(i * i)); check(null == map.getObject(i * i));
   * map.remove(i * i); check(!map.isObjectType(i * i)); check(!map.isIntType(i
   * * i)); }
   * 
   * int old_size = map.size(); for (int i = 0; i != N; ++i) { map.remove(i *
   * i); check(map.size() == old_size); }
   * 
   * System.out.print("."); System.out.flush(); map.clear(); check(map.size() ==
   * 0); for (int i = 0; i != N; ++i) { map.put(i * i, i); map.put(i * i + 1,
   * new Double(i+0.5)); } checkSameMaps(map, (UintMap)writeAndRead(map));
   * 
   * System.out.print("."); System.out.flush(); map = new UintMap(0);
   * checkSameMaps(map, (UintMap)writeAndRead(map)); map = new UintMap(1);
   * checkSameMaps(map, (UintMap)writeAndRead(map)); map = new UintMap(1000);
   * checkSameMaps(map, (UintMap)writeAndRead(map));
   * 
   * System.out.print("."); System.out.flush(); map = new UintMap(N / 10); for
   * (int i = 0; i != N; ++i) { map.put(2*i+1, i); } checkSameMaps(map,
   * (UintMap)writeAndRead(map));
   * 
   * System.out.print("."); System.out.flush(); map = new UintMap(N / 10); for
   * (int i = 0; i != N; ++i) { map.put(2*i+1, i); } for (int i = 0; i != N / 2;
   * ++i) { map.remove(2*i+1); } checkSameMaps(map, (UintMap)writeAndRead(map));
   * 
   * System.out.print("."); System.out.flush(); map = new UintMap(); for (int i
   * = 0; i != N; ++i) { map.put(2*i+1, new Double(i + 10)); } for (int i = 0; i
   * != N / 2; ++i) { map.remove(2*i+1); } checkSameMaps(map,
   * (UintMap)writeAndRead(map));
   * 
   * System.out.println(); System.out.flush();
   * 
   * }
   * 
   * private static void checkSameMaps(UintMap map1, UintMap map2) {
   * check(map1.size() == map2.size()); int[] keys = map1.getKeys();
   * check(keys.length == map1.size()); for (int i = 0; i != keys.length; ++i) {
   * int key = keys[i]; check(map2.has(key)); check(map1.isObjectType(key) ==
   * map2.isObjectType(key)); check(map1.isIntType(key) == map2.isIntType(key));
   * Object o1 = map1.getObject(key); Object o2 = map2.getObject(key); if
   * (map1.isObjectType(key)) { check(o1.equals(o2)); }else {
   * check(map1.getObject(key) == null); check(map2.getObject(key) == null); }
   * if (map1.isIntType(key)) { check(map1.getExistingInt(key) ==
   * map2.getExistingInt(key)); }else { check(map1.getInt(key, -10) == -10);
   * check(map1.getInt(key, -11) == -11); check(map2.getInt(key, -10) == -10);
   * check(map2.getInt(key, -11) == -11); } } }
   * 
   * private static void check(boolean condition) { if (!condition)
   * Kit.codeBug(); }
   * 
   * private static Object writeAndRead(Object obj) { try {
   * java.io.ByteArrayOutputStream bos = new java.io.ByteArrayOutputStream();
   * java.io.ObjectOutputStream out = new java.io.ObjectOutputStream(bos);
   * out.writeObject(obj); out.close(); byte[] data = bos.toByteArray();
   * java.io.ByteArrayInputStream bis = new java.io.ByteArrayInputStream(data);
   * java.io.ObjectInputStream in = new java.io.ObjectInputStream(bis); Object
   * result = in.readObject(); in.close(); return result; }catch (Exception ex)
   * { ex.printStackTrace(); throw new RuntimeException("Unexpected"); } }
   * 
   * // TEST END
   */
}
